package algorithm.recursionAndbacktrack.twoDimensions.p79;

/**
 * @Author CandyWall
 * @Date 2022/2/5--9:01
 * @Description 79. 单词搜索
 */
public class Solution {
    private int m, n;
    private boolean[][] visited;
    private int[][] d = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
    public boolean exist(char[][] board, String word) {
        if(board != null)
            m = board.length;
        if (m > 0)
            n = board[0].length;
        if (m > 0 && n > 0) {
            visited = new boolean[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if(searchWord(board, word, 0, i, j)) {
                        return true;
                    }
                }
            }

        }

        return false;
    }

    private boolean searchWord(char[][] board, String word, int index, int startX, int startY) {
        if (index == word.length() - 1) {
            return board[startX][startY] == word.charAt(index);
        }

        if (board[startX][startY] == word.charAt(index)) {
            visited[startX][startY] = true;
            // 从startX和startY出发，向四个方向寻找
            for (int i = 0; i < d.length; i++) {
                int newX = startX + d[i][0];
                int newY = startY + d[i][1];
                if (inArea(newX, newY) && !visited[newX][newY] && searchWord(board, word, index + 1, newX, newY))
                    return true;
            }
            visited[startX][startY] = false;
        }
        return false;
    }

    // 判断坐标是否合法
    private boolean inArea(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},
                          {'S','F','C','S'},
                          {'A','D','E','E'}};
        // System.out.println(new Solution().exist(board, "ABCCED"));
        System.out.println(new Solution().exist(board, "BFCCESEEDA"));
    }
}
